#include <map>
#include <stdio.h>
#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include <time.h>

#include "common.h"
#include "function.h"

using namespace std;

bool Function::AddDependent (Function* f) 
{
    if (ContainsDependent (f))
        return false;
    dependents.push_back (f);
    return true;
}

bool Function::ContainsDependent (Function* f) 
{
    vector<Function*>::iterator it = dependents.begin();
    
    while (it != dependents.end()) {
        if (*it == f)
            return true;
        it++;        
    }
    return false;
}


void Processor::Print() 
{
    std::list<Function*>::iterator it = assignments.begin();
    while (it != assignments.end()) {
        printf ("%s ", (*it)->name);
        it++;
    }
}


CallGraph::~CallGraph() 
{  
    std::list<Function*>::iterator it = graph.begin();
    while (it != graph.end()) {
        delete *it;
        it++;
    }
}   


CallGraph::Enumeration CallGraph::GetEnumeration() 
{
    std::list<Function*> roots;
    std::list<Function*>::iterator it = graph.begin();
    while (it != graph.end()) {
        if ((*it)->dependencies == 0)
            roots.push_back (*it);
        it++;
    }
    return Enumeration (roots);
}

void CallGraph::Print()
{
    printf ("\n\nGraph: ");
    std::list<Function*>::iterator it = graph.begin();
    while (it != graph.end()) {
        printf ("%s-(%d)  ", (*it)->name, (*it)->time);
        it++;
    }
    printf ("\n\n");
    
}

void CallGraph::SetRandomTime()
{
    std::list<Function*>::iterator it = graph.begin();
    while (it != graph.end()) {
        (*it)->time = 1 + rand() % 9;
        it++;
    }
    
}

Processor* CallGraph::Schedule (int n) 
{
    assert (n > 0);
    
    Processor* p = new Processor[n];        // Temporary assignment
    int pTime;          
    Processor* bestSol = new Processor[n];  // Best assignment solution
    int bestTime = INT_MAX;
    
    Enumeration en = GetEnumeration();        
    
    while (en.HasMoreElements()) {
        list<Function*>& calls = en.NextElement();
        pTime = 0;
        int insert = 0;                 // Index of the processor with the lowest workload
        map<Function*,int> actualTime;  // Map to keep track of the actual time required by each function
                    
        list<Function*>::iterator it = calls.begin();
        while (it != calls.end()) {
            
            // Update actual time
            int t = actualTime[*it] += (*it)->time;            
            
            // Update actual time for dependents
            for (int i=0; i<(*it)->dependents.size(); i++) {
                int& actTime = actualTime[(*it)->dependents[i]];
                
                if (t > actTime)
                    actTime = t;
            }
            
            // Assign current function to current processor
            p[insert].AddAssignment (*it, t);
            
            // Update assignment time
            int execTime = p[insert].GetExecTime();
            pTime = execTime > pTime ? execTime : pTime ;
            
            // Update insert index 
            for (int i=0; i<n; i++) 
                if (p[i].GetExecTime() < p[insert].GetExecTime())
                    insert = i;                                
                
            it++;
        }     
        
//         // DEBUG
//         // Print current solution
//         int totalTime = 0;
//         Processor* assignments = p;        
//         for (int i=0; i<n; i++) {
//             printf ("\nProcessor %d: ", i);
//             assignments[i].Print();
//             int t = assignments[i].GetExecTime();
//             totalTime = t > totalTime ? t : totalTime;
//         }
//         printf ("\nTotal time = %d\n\n", totalTime);
        
        
        if (pTime < bestTime) {       
            // Swap pointers
            Processor* tmp = p;
            p = bestSol;
            bestSol = tmp;
            
            // Update best solution time
            bestTime = pTime;
        }
        
        // Clear processors for next iteration
        for (int i=0; i<n; i++)
            p[i].Clear();
    }
    
    delete [] p;
    
    return bestSol;
}



CallGraph::Enumeration::Enumeration (Function* root) { 
    list<Function*>* l = new list<Function*>();
    l->push_back (root);
    choices.push (l); 
    indices.push (l->begin());
}


CallGraph::Enumeration::Enumeration (list<Function*>& roots) { 
    list<Function*>* l = new list<Function*> (roots);    
    choices.push (l); 
    indices.push (l->begin());
}

CallGraph::Enumeration::~Enumeration()
{
    while (choices.size())
        delete choices.top();            
}

bool CallGraph::Enumeration::HasMoreElements() 
{    
    // Clear "calls" list for next element and restore depedencies
    while (calls.size() && calls.size() >= choices.size()) {
        Function* f = calls.back();
        for (int i=0; i<f->dependents.size(); i++)
            f->dependents[i]->dependencies++;
        
        calls.pop_back();
    }
    return choices.size();
}

list<Function*>& CallGraph::Enumeration::NextElement() 
{              
    while (choices.top()->size()) {
        list<Function*>* currChoices = choices.top();
        list<Function*>::iterator& currIndex = indices.top();
        
        Function* f = *currIndex;    
        list<Function*>* newChoices = new list<Function*> (*currChoices);        
                
        newChoices->remove (f);
        currIndex++;
        
        for (int i=0; i<f->dependents.size(); i++)                    
            if (--(f->dependents[i]->dependencies) == 0)  // If there are no more dependencies 
                newChoices->push_back (f->dependents[i]);            
            
        calls.push_back (f);                 
        choices.push (newChoices); 
        indices.push (newChoices->begin());
    }
           
    // Clear status for next call
    while (choices.size() && choices.top()->end() == indices.top()) {
        delete choices.top();
        choices.pop();
        indices.pop();
    }
    
    return calls;
}

